/**
 * Created with IntelliJ IDEA.
 * Description: 优化快速排序有序数组情况下递归深度过深的问题
 * User: liangyuanzhang
 * Date: 2025/7/12
 * Time: 10:52
 */

/*
优化的方法是三数取中法
 */

public class OptimizedQuickSort {

    public static void print(int[] array){ //打印方法
        for (int i = 0;i < array.length;i++){
            System.out.print(array[i]+" ");
        }
    }

    public static void main(String[] args) {
        System.out.println("hello quicksort!");
        int[] array = {10,9,8,7,6,5,4,3,2,1};
        quicksort(array);
        print(array);
    }

    public static void quicksort(int[] array){ //快速排序
        quick(array,0, array.length-1);
    }

    private static void quick(int[] array,int start,int end){ //分层
        if (start >= end){
            return;
        }

        int minIndex = getMiddleNum(array,start,end);
        swap(array,start,minIndex);

        int pivot = partition(array,start,end);
        quick(array,start, pivot-1);
        quick(array,pivot+1,end);
    }

    private static int getMiddleNum(int[] array,int left,int right){ //这个方法就是优化的地方
        int mid = (left+right)/2;
        if (array[left] < array[right]){
            if (array[mid] < array[left]){
                return left;
            }else if (array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }else {
            if (array[mid] < array[right]){
                return right;
            }else if (array[mid] > array[left]){
                return left;
            }else{
                return mid;
            }
        }
    }

    private static int partition(int[] array,int left,int right){ //排序过程
        int tmp = array[left];
        int tmpLeft = left;
        while (left < right){
            while (left < right && array[right] >= tmp){
                right--;
            }
            //可以用挖坑法
            while (left < right && array[left] <= tmp){
                left++;
            }
            swap(array, left, right);//可以改成挖坑法
        }
        swap(array, tmpLeft, right);//挖坑法完成后这里交换可以改成把原来的基准放到坑里
        return left;
    }

    public static void swap(int[] array,int left,int right){ //交换方法
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }

}